import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;




//方法1
/*
给定一个二叉树 root ，返回其最大深度。

        二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
        输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：

输入：root = [1,null,2]
输出：2



class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int D1 = maxDepth(root.left);
        int D2 = maxDepth(root.right);
        return Integer.max(D1,D2) + 1;

    }
}
//方法2
class Solution {
    public int maxDepth(TreeNode root) {
        TreeNode curr = root;
        TreeNode pop = null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int max = 0;
        while(curr != null || !stack.isEmpty()){
            if(curr != null){
                stack.push(curr);
                int size = stack.size();
                if(size > max){
                    max = size;
                }
                curr = curr.left;
            }else{
                TreeNode peek = stack.peek();
                if(peek.right == null || peek.right == pop){
                    pop =   stack.pop();
                }else{
                    curr = peek.right;
                }
            }
        }
        return max;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode>  queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size = queue.size();;
            for(int i = 0; i < size;i++){
                TreeNode poll = queue.poll();
                if(poll.left != null){
                    queue.offer(poll.left);
                }
                if(poll.right != null){
                    queue.offer(poll.right);
                }
            }
            depth++;
        }

           return  depth;
    }
}*/